#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <cassert>

using namespace std;
typedef char DataType;

typedef struct LinkNode
{
    DataType data;
    LinkNode *next;
} LinkNode;

// 打印链表
void printf(LinkNode *p)
{
    LinkNode *current = p;
    while (current)
    {
        printf("%c->", current->data);
        current = current->next;
    }
    printf("NULL");
    printf("\n");
}

// 节点查询
LinkNode *SLTNodeFind(LinkNode *head, DataType d)
{
    LinkNode *p = head;
    int x = 1;
    while (p)
    {
        if (p->data == d)
        {
            printf("链表第%d位\n", x);
            return p;
        }
        else
        {
            x++;
            p = p->next;
        }
    }
    return NULL;
}
// 创建链表节点
LinkNode *initLinkList(DataType d)
{
    LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
    p->data = d;
    p->next = NULL;
    return p;
}

// 单链表尾插
void insertTail(LinkNode *p, LinkNode **head)
{

    if (*head == NULL)
    {
        *head = p;
    }
    else
    {
        LinkNode *tail = *head;
        while (tail->next)
        {
            tail = tail->next;
        }
        tail->next = p;
    }
}
// 单链表尾删
void deleteTail(LinkNode **head)
{

    LinkNode *current = *head;
    if (head = NULL)
    {
        printf("单链表为空");
        return;
    }
    if (current->next == NULL)
    {
        free(*head);
        *head = NULL;
    }
    else
    {

        while (current->next->next)
        {
            current = current->next;
        }
        free(current->next);
        current->next = NULL;
    }
}
// 单链表头删
void deleteHead(LinkNode **head)
{
    LinkNode *current = *head;
    if (current = NULL)
    {
        printf("单链表为空");
        return;
    }
    *head = (*head)->next;
    free(current);
}
// 单链表头插
LinkNode *insertHead(LinkNode *p, LinkNode **head)
{
    LinkNode *h = *head;
    p->next = h;
    return p;
}
// 节点尾插
void insertbyselectTail(LinkNode *p, LinkNode **head, DataType x)
{
    LinkNode *current = *head;
    while (current != p)
    {
        current = current->next;
    }
    LinkNode *newNode = initLinkList(x);
    newNode->next = current->next;
    current->next = newNode;
}
// 节点头插
void insertByselectHead(LinkNode *p, LinkNode **head, DataType x)
{
    LinkNode *current = *head;
    while (current->next != p)
    {
        current = current->next;
    }
    LinkNode *newNode = initLinkList(x);
    newNode->next = current->next;
    current->next = newNode;
}
// 节点删除
void deleteNode(LinkNode *head, DataType x)
{
    LinkNode *p = SLTNodeFind(head, x);
    while (head->next != p)
    {
        head = head->next;
    }
    head->next = p->next;
}
int main()
{
    LinkNode *head = NULL;
    LinkNode *p;
    LinkNode **phead;
    char data;
    char choise;
    char exit_choice;
    while (1)
    {
        printf("请选择操作：\n");
        printf("P. 输出单链表\n");
        printf("T. 单链表尾插\n");
        printf("H. 单链表头插\n");
        printf("Y. 单链表尾删\n");
        printf("X. 单链表头删\n");
        printf("C. 单链表节点查询\n");
        printf("W. 节点尾插\n");
        printf("O. 节点头插\n");
        printf("U. 节点修改\n");
        printf("D. 节点删除\n");
        printf("Z. 销毁链表\n");
        printf("E. 退出\n");
        scanf(" %c", &choise);
        switch (choise)
        {
        case 'Z':
            p = head;
            while (p = NULL)
            {
                head = head->next;
                free(p);
            }
            head = NULL;
            break;
        case 'D':
            printf("你选择了节点删除:\n");
            printf("输入你想删除的节点:\n");
            scanf(" %c", &data);
            deleteNode(head, data);
            break;
        case 'U':
            printf("你选择了节点修改:\n");
            printf("输入你想修改的节点:\n");
            scanf(" %c", &data);
            p = SLTNodeFind(head, data);
            printf("输入你想修改的节点元素:\n");
            scanf(" %c", &data);
            p->data = data;
            break;
        case 'O':
            printf("你选择了节点头插操作:\n");
            printf("输入你想插入的节点:\n");
            scanf(" %c", &data);
            p = SLTNodeFind(head, data);
            printf("输入你想在此前插入的节点元素:\n");
            scanf(" %c", &data);
            **phead = *head;
            insertByselectHead(p, phead, data);
            break;
        case 'W':
            printf("你选择了节点尾插操作:\n");
            printf("输入你想插入的节点:\n");
            scanf(" %c", &data);
            p = SLTNodeFind(head, data);
            printf("输入你想在此后插入的节点元素:\n");
            scanf(" %c", &data);
            **phead = *head;
            insertbyselectTail(p, phead, data);
            break;
        case 'C':
            printf("你选择了单链表节点查询操作:\n");
            printf("输入你想查找的节点元素:\n");
            scanf(" %c", data);
            SLTNodeFind(head, data);
            break;
        case 'X':
            printf("你选择了单链表头删操作\n");
            **phead = *head;
            deleteHead(phead);
            break;
        case 'Y':
            printf("你选择了单链表尾删操作\n");
            **phead = *head;
            deleteTail(phead);
            break;
        case 'P':
            printf("你选择了打印操作\n");
            printf(head);
            break;
        case 'T':
            printf("你选择了单链表尾插操作,请输入新节点元素：\n");
            scanf(" %c", &data);
            p = initLinkList(data);
            phead = &head;
            insertTail(p, phead);
            break;
        case 'H':
            printf("你选择了单链表头插操作,请输入新节点元素：\n");
            scanf(" %c", &data);
            p = initLinkList(data);
            phead = &head;
            head = insertHead(p, phead);
            break;
        case 'E':
            printf("您确定要退出吗？按E键确认退出，按其他键返回上级菜单。\n");
            scanf(" %c", &exit_choice); // 加上空格忽略换行符
            if (exit_choice == 'E' || exit_choice == 'e')
            {
                printf("谢谢使用，再见！\n");
                return 0;
            }
            break;
        default:
            printf("无效的选择，请重新选择。\n");
            break;
        }
    }
}
